package 算法.NiuKe.JZ;

import java.util.Arrays;

/**
 * @author: 谢君臣
 * @create: 2021-01-25 21:10
 * @founction: XXXX
 * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
 * 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
 * NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
 */
public class JZ6 {
    public static void main(String[] args) {
        int[] array = {3,4, 5, 6,7,7,8 ,1, 2, 3};
        System.out.println(minNumberInRotateArray(array));
    }

    public static int minNumberInRotateArray(int[] array) {
        if (array.length == 0)
            return 0;
        else {
            return findMin(array);
        }
    }

    private static int findMin(int[] array) {
        if (array.length == 1)
            return array[0];
        else {
            if (array.length == 2)
                return Math.min(array[0], array[1]);
            int mid = array.length / 2;
            if (array[mid - 1] <= array[mid] && array[mid] <= array[mid + 1]) {
                if (array[array.length-1]>=array[mid])
                    return findMin(Arrays.copyOfRange(array,0,mid+1 ));
                else
                    return findMin(Arrays.copyOfRange(array,mid+1,array.length));
            } else
                return Math.min(array[mid], array[mid + 1]);
        }
    }
}
